分布式数据库简答题，分片设计，存取优化，查询优化，计算代价
目录
1. 九八年秋季试题 ............................................................. 5
1.1. 概念题 .............................................................. 5
1.1.1. 比较半连接方法和枚举法的优缺点。 ................................. 5
1.1.2. 2PL协议的基本思想。 .............................................. 5
1.1.3. WAL协议的主要思想。 .............................................. 5
1.1.4. SSPARC三级模式体系结构。 ......................................... 5
1.1.5. 设计OID的数据结构时应考虑哪些问题。 .............................. 6
1.2. 某个大学中有若干系，且每个系有若干个班级和教研室，每个教研室有若干个教
员，其中教授、副教授每个人带若干名研究生。每个班有若干名学生，每个学生可选修
若干门课程，每门课程可由若干学生选修。完成下列各种要求： ................... 7
1.3. 下面是某学院的一个学生档案数据库的全局模式： ........................ 9
1.3.1. 将全局模式进行分片，写出分片定义和分片条件。 ..................... 9
1.3.2. 指出各分片的类型，并画出分片树。 ................................. 9
1.3.3. 假设要求查询系号为1的所有学生的姓名和成绩，写出在全局模式上的SQL查
询语句，并要求转换成相应的关系代数表示，画出全局查询树，请依次进行全局优化
和分片优化，画出优化后的查询树。要求给出优化变换过程。 ................. 10
1.4. 设数据项x,y存放在S1场地，u,v存放在S2场地，有分布式事务T1和T2,T1在S1场
地的操作为R1(x)W1(x)R1(y)W1(y),T2在S1场地的操作为R2(x)R2(y)W2(y);T1在S2场地
上的操作作为R1(u)R1(v)W1(u),T2在S2场地上的操作作为W2(u)R2(v)W2(v)。对下述2种
情况，各举一种可能的局部历程（H1和H2），并说明理由。 ....................... 11
1.4.1. 局部分别是可串行化，而全局是不可串行化的 ........................ 11
1.4.2. 局部和全局都是可串行化的。要求按照严格的2PL协议，加上适当的加锁和解
锁命令，（注意，用rl(x)表示加读锁，wl(x)表示加对x加写锁，ul(x)表示解锁） 12
1.5. 试述面向对象的数据库系统中页面服务器和对象服务器两种Client/Server体系
结构的主要特点, ........................................................... 12
2. 九九年春季试题 ............................................................ 13
2.1. DBMS解决了信息处理技术中的哪些挑战？ ............................... 13
2.2. 在关系数据库应用设计中，为什么要对数据库模式进行规范化？ ........... 13
2.3. 简述ACID特性。 ..................................................... 15
2.4. 长事务处理有哪些特性，如何解决？ ................................... 15
2.5. 数据库系统体系结构有哪几类，每种类型的特点是什么，关键技术有哪些？ . 16
2.6. 决策支持类应用与OLTP应用对于数据库系统的要求有哪些不同，支持前者的关键
技术有哪些，并简述之。 .................................................... 17
2.7. 面向对象的数据库是如何产生的，其基本原理是什么？有哪些创新特性？ ... 18
2.8. r i ∝ r
j 一定等于r j
∝ r i 吗？在什么条件下r i ∝ r
j = r j
∝ r i 成立? ......... 18
2.9. 为了设计一个健壮的分布式系统，你必须知道可能发生哪种类型的失败。 ... 18
2.9.1. 请列出在分布式系统中可能的失败类型： ............................ 18
2.9.2. 在你列出的失败类型中，哪些也可能发生在集中式系统中？ ............ 19
2.9.3. 对于每一种失败类型，在失败发生情况下，两段提交机制如何保证事务的原
子性？ 19
3. 九九年秋季试题 ............................................................ 19
3.1. 问答题 ............................................................. 19
3.1.1. 分布式数据库系统在系统结构、模式结构、功能模块等方面有何特点？ .. 19
3.1.2. 给出两种2PL协议，并比较它们的优点缺点？ ......................... 20
3.1.3. 解释为什么对象类的多继承存在二义性，并通过例子加以说明。 ........ 20
3.1.4. 对于下述情况，哪种并行性（查询间并行性、操作间并行性、操作内并行性）
有助于正加系统的吞吐量： ............................................... 20
3.2. 下面是某个公司人事数据库的两个全局关系 ............................. 20
3.2.1. 将全局模式进行分片，写出分片定义和分片条件。 .................... 20
3.2.2. 指出各分片的类型，并画出分片树 .................................. 21
3.2.3. 进行全局优化，画出优化后的全局查询树。 .......................... 21
3.2.4. 进行分片优化，画出优化后的分片查询树。 .......................... 22
3.3. 对3个关系R,S和T的分布式连接，已知有如下的剖视图： .................. 25
3.3.1. 按照SDD-1半连接优化算法，逐步求出半连接优化集和最终执行场地； ... 25
3.3.2. 对以上结果做相应的优化处理。 .................................... 31
3.4. 用下面的关键字值的集合构造一颗B 树：（2,3,5,7,11,17,19,23,29,31）。假定
树开始是空的，且关键字的值是以升序插入到B 树中去的，B 树每个节点中含的指针数
为4。 32
3.5. 考虑关系r
1 (A,B,C)，r 2
(C,D,E)，r
3
(E,F)，假设不存在主关键字。设V(C,
r 1 )=900， ................................................................. 32
3.6. 假设一个存储块中仅能存放一个记录且在内存中最多只有三个页框。请 出在排
序合并算法中每遍形成的Runs,排序属性为第一个属性：（kangaroo,17），(wallaby,21)，
(emu,1)，(wombat,13)，(platypus,3)，(lion,8)，(warthg,4)，(zebra,11)，(meerkat,6)，
(hornbill,2)，(baboon,12)。 ............................................... 32
4. 二零年春季试题 ............................................................ 32
4.1. ...................................................................... 32
4.1.1. 分布库管理系统有哪些主要功能模块及其作用. ....................... 32
4.1.2. 半连接方法和枚举法各适用于何种查询优化情况. ..................... 32
4.1.3. 分布式事务有哪些基本性质. ....................................... 32
4.1.4. 什么是2PL协议 ................................................... 33
4.2. 下面是某个公司的人事关系数据库的全局模式： ......................... 33
4.2.1. 将全局模式进行分片，写出分片定义和分片条件。 .................... 34
4.2.2. 指出分片的类型，并画出分片树。 .................................. 34
4.3. 对题4.2所确定的分片模式，要求查询级别高于“6”的所有职员的姓名和工资，
写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询
树。 34
4.3.1. 进行全局优化，画出各步优化后的全局查询树。 ...................... 34
4.3.2. 进行分片优化，画出各步优化后的分片查询树。 ...................... 35
4.4. 下面是一个数据库系统出现故障是，日志文件中记录的信息； ............. 36
4.4.1. 找出发生故障时系统中的活动事务，确定出反做和重做事务集。 ........ 36
4.4.2. 用C或其他语言定义出数据库记录（D记录）和检查点记录（K记录）的数据结
构。 36
4.5. 设数据项x,y存放在S1场地，u,v存放在S2场地，有分布式事务T1和T2,T1在S1场
地的操作为R1(x)W1(x)R1(y)W1(y),T2在S1场地的操作为R2(x)R2(y)W2(y);T1在S2场地
上的操作作为R1(u)R1(v)W1(u),T2在S2场地上的操作作为W2(u)R2(v)W2(v)。对下述2种
情况，各举一种可能的局部历程（H1和H2），并说明理由 ......................... 36
4.5.1. 局部分别是可串行化，而全局是不可串行化的 ........................ 37
4.5.2. 局部和全局都是可串行化的。 ...................................... 37
4.5.3. 要求按照严格的2PL协议，加上适当的加锁和解锁命令，（注意，用rl(x)表示
加读锁，wl(x)表示加对x加写锁，ul(x)表示解锁） .......................... 37
5. 二零年秋试题 .............................................................. 38
5.1. 概念题 ............................................................. 38
5.1.1. 解释对象数据库系统中面向对象的相关概念 .......................... 38
5.1.2. 从概念上比较对象数据库模型与对象关系模型 ........................ 38
5.1.3. 利用左深树、右深树、浓密树来进行查询优化的各自特点 .............. 38
5.1.4. 试解释影响并行数据库系统中并行算法性能的三个因数 ................ 39
5.1.5. 简述用爬山算法进行查询优化的基本思想 ............................ 39
5.2. 下 面 是 某 个 公 司 一 个 人 事 关 系 数 据 库 的 全 局 模 式 ：
EMP={ENO*,ENAME,POSITION,PHONE} PAY={POSITION*,SALARY} ENO为职员号，
POSITION为岗位。SALARY表示岗位对应的工资，*对应的属性表示主关键字。该公司分布
在两个场地上，其中，在场地1经常处理所有职员数据，而场地2只处理工资低于1000的
职员数据，为了节省磁盘空间和增大处理局部性： .............................. 40
5.2.1. 将以上全局关系进行分片设计，写出分片定义和分片条件。 ............ 40
5.2.2. 指出分片的类型，并画出分片树。 .................................. 40
5.2.3. 给出分配设计。 .................................................. 40
5.3. 对题二所确定的分片模式，要求查询岗位为“salesman”的所有职员的姓名和工
资，写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局
查询树。假设“salesman”的工资为800元。要求给出中间转换过程。 ............. 41
5.3.1. 进行全局优化，画出优化后的全局查询树。 .......................... 41
5.3.2. 进行分片优化，画出优化后的分片查询树。 .......................... 42
5.4. 按如下给出的条件，求出半连接优化计划和执行场地，并作后优化处理 ..... 42
5.5. 下面是当一个数据库系统出现故障时，日志文件中的信息 ................. 48
5.5.1. 画出对应的事务并发执行图。 ...................................... 49
5.5.2. 找出发生故障时系统中的活动事务，确定出反做和重做事务集。 ........ 49
5.5.3. 指出需要undo的和redo的数据记录。 ................................ 49
5.6. 设数据项x,y存放在S1场地，u,v存放在S2场地，有分布式事务T1和T2。T1在S1场
地的操作为R1(x)W1(x)R1(y)W1(y)，T2在S1场地的操作为R2(x)R2(y)W2(y)；T1在S2场地
上的操作作为R1(u)R1(v)W1(u)，T2在S2场地上的操作作为W2(u)R2(v)W2(v)。对下述2种
情况，各举一种可能的局部历程（H1和H2），如果是可串行化的，指出事务的执行次序。
对第3种情况，给出符合基本2PL协议的调度。（T1 加锁命令用L1(X)表示，开锁命令U1(X)
表示。对任何数据的加锁可在事务开始后立即进行）。 ........................... 49
5.6.1. 局部是不可串行化的。 ............................................ 50
5.6.2. 局部是可串行化的，而全局是不可串行化的。 ........................ 50
5.6.3. 局部是可串行化的，全局也是可串行化的。 .......................... 51
5.7. 设计一种满足下列要求的索引结构。 ................................... 51
5.7.1. 被索引的数据集合为有序集 ........................................ 51
5.7.2. 在有序集上的查询操作都是基于位置来进行的 ........................ 51
5.7.3. 当往有序集中插入或删除一个元素时，与该元素相关的后续元素的位置均要
发生变化 ............................................................... 51
5.7.4. 元素的类型可为任意类型（这一个小问题的解决需要考虑语言的特征） .. 51
6. 二零一春季试题 ............................................................ 51
6.1. ...................................................................... 51
6.1.1. 讨论集中式数据库和分布式数据库各自的优缺点。 .................... 51
6.1.2. 讨论在局域网和广域网两种情况下分布库设计的区别。 ................ 52
6.1.3. 解释分片透明性、复制透明性和位置透明性等三级透明性的区别。 ...... 52
6.1.4. 解释2PC协议如何在故障情况下保证事务的原子性的 ................... 52
6.1.5. 解释严格2PL协议与基本2PL协议的区别 .............................. 53
6.2. 下 面 是 某 个 公 司 一 个 人 事 关 系 数 据 库 的 全 局 模 式 ：
EMP={ENO*,ENAME,POSITION,PHONE} PAY={POSITION*,SALARY} ENO为职员号，
POSITION为岗位。SALARY表示岗位对应的工资，*对应的属性表示主关键字。该公司分布
在两个场地上，其中，在场地1经常处理所有职员数据，而场地2只处理工资低于1000的
职员数据，为了节省磁盘空间和增大处理局部性： .............................. 54
6.2.1. 将以上全局关系进行分片设计，写出分片定义和分片条件。 ............ 54
6.2.2. 指出分片的类型，并画出分片树。 .................................. 54
6.2.3. 给出分配设计。 .................................................. 54
6.3. 对题二所确定的分片模式，要求查询岗位为“salesman”的所有职员的姓名和工
资，写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局
查询树。假设“salesman”的工资为1500元。要求给出中间转换过程。 ............ 55
6.3.1. 进行全局优化，画出优化后的全局查询树 ............................ 55
6.3.2. 进行分片优化，画出优化后的分片查询树。 .......................... 56
6.4. 下面是当一个数据库系统出现故障时，日志文件中的信息 ................. 56
6.4.1. 画出对应的事务并发执行图。 ...................................... 57
6.4.2. 找出发生故障时系统中的活动事务，确定出反做和重做事务集。 ........ 58
6.4.3. 指出需要undo的和redo的数据记录。 ................................ 58
6.5. 设数据项x,y存放在S1场地，u,v存放在S2场地，有分布式事务T1和T2,T1在S1场
地的操作为R1(x)W1(x)R1(y)W1(y),T2在S1场地的操作为R2(x)R2(y)W2(y);T1在S2场地
上的操作作为R1(u)R1(v)W1(u),T2在S2场地上的操作作为W2(u)R2(v)W2(v)。对下述2种
情况，各举一种可能的局部历程（H1和H2），如果是可串行化的，指出事务的执行次序。
对第3种情况，给出符合基本2PL协议的调度。（T1 加锁命令用L1(X)表示，开锁命令U1(X)
表示。对任何数据的加锁可在事务开始后立即进行）。 ........................... 58
6.5.1. 局部是不可串行化的。 ............................................ 58
6.5.2. 局部是可串行化的，而全局是不可串行化的。 ........................ 59
6.5.3. 局部是可串行化的，全局也是可串行化的。 .......................... 59
评论